<!DOCTYPE html>



  


<html class="theme-next pisces use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">
<meta name="referrer" content="same-origin">
<meta name="referrer" content="no-referrer" />








<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="算法国," />










<meta name="description" content="&amp;emsp;&amp;emsp;本故事除了算法纯属虚构。  算法就是思考的方式  很长的开头&amp;emsp;&amp;emsp;很久以前，算法国的人只知道0和1。有一天，来了一个外国人，外国人会一种新奇的语言，它简单却又多变，生动而且内涵，它有二十六个字母组成，对比可怜又枯燥的0和1，这实在太有趣了！算法国的人一下子爱上了这种语言。外国人很开心算法国的人喜欢他们的语言，于是他很慷慨地教他们，他大笔一挥，写下算法国第一">
<meta name="keywords" content="算法国">
<meta property="og:type" content="article">
<meta property="og:title" content="算法国（二）字符串匹配">
<meta property="og:url" content="http://yoursite.com/2018/12/17/算法国（二）字符串匹配/index.html">
<meta property="og:site_name" content="矩阵编程">
<meta property="og:description" content="&amp;emsp;&amp;emsp;本故事除了算法纯属虚构。  算法就是思考的方式  很长的开头&amp;emsp;&amp;emsp;很久以前，算法国的人只知道0和1。有一天，来了一个外国人，外国人会一种新奇的语言，它简单却又多变，生动而且内涵，它有二十六个字母组成，对比可怜又枯燥的0和1，这实在太有趣了！算法国的人一下子爱上了这种语言。外国人很开心算法国的人喜欢他们的语言，于是他很慷慨地教他们，他大笔一挥，写下算法国第一">
<meta property="og:locale" content="zh-Hans">
<meta property="og:updated_time" content="2019-10-24T16:22:00.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="算法国（二）字符串匹配">
<meta name="twitter:description" content="&amp;emsp;&amp;emsp;本故事除了算法纯属虚构。  算法就是思考的方式  很长的开头&amp;emsp;&amp;emsp;很久以前，算法国的人只知道0和1。有一天，来了一个外国人，外国人会一种新奇的语言，它简单却又多变，生动而且内涵，它有二十六个字母组成，对比可怜又枯燥的0和1，这实在太有趣了！算法国的人一下子爱上了这种语言。外国人很开心算法国的人喜欢他们的语言，于是他很慷慨地教他们，他大笔一挥，写下算法国第一">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://yoursite.com/2018/12/17/算法国（二）字符串匹配/"/>





  <title>算法国（二）字符串匹配 | 矩阵编程</title>
  





  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?7d29e6fba8e07d1a8af2414a20e5f2a6";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">矩阵编程</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-主页">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-主页"></i> <br />
            
            主页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-分类"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-所有文章">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-文章"></i> <br />
            
            所有文章
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2018/12/17/算法国（二）字符串匹配/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="matrix">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="矩阵编程">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">算法国（二）字符串匹配</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-12-17T22:22:55+08:00">
                2018-12-17
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/算法国/" itemprop="url" rel="index">
                    <span itemprop="name">算法国</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/2018/12/17/算法国（二）字符串匹配/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count disqus-comment-count"
                        data-disqus-identifier="2018/12/17/算法国（二）字符串匹配/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>&emsp;&emsp;本故事除了算法纯属虚构。</p>
<blockquote>
<p><strong>算法就是思考的方式</strong></p>
</blockquote>
<h4 id="很长的开头"><a href="#很长的开头" class="headerlink" title="很长的开头"></a>很长的开头</h4><p>&emsp;&emsp;很久以前，算法国的人只知道0和1。有一天，来了一个外国人，外国人会一种新奇的语言，它简单却又多变，生动而且内涵，它有二十六个字母组成，对比可怜又枯燥的0和1，这实在太有趣了！算法国的人一下子爱上了这种语言。外国人很开心算法国的人喜欢他们的语言，于是他很慷慨地教他们，他大笔一挥，写下算法国第一行外文：</p>
<blockquote>
<p><strong>“Hello World。”</strong></p>
</blockquote>
<a id="more"></a>
<p>&emsp;&emsp;他不知道这一行外文，今后会在算法国永垂不朽。算法国的人很聪明，他们还用1和0来翻译了所有外文，从此外文和他们的方言可以无缝衔接。他们还把外文称为高级语言，1和0就变成了低级语言。他们用高级语言写算法，写着写着就打起来了，每个人写得算法都不一样，每个人的信仰也变得不一样，后来愈演愈烈，水火不容，终于引发了著名的茴香豆大战。<br>&emsp;&emsp;算法国的人虽然学了外文，也翻译了外文，但是他们学不了外文那么多变化。他们的内心其实只容得下1和0，虽然改变了语言，但是改变不了思维。后来他们觉得只要学几个关键字就够了，比如他们学会了final，学会constant，他们知道这两个词代表誓言，誓言永不变———谁也不能背叛誓言，在算法国，背叛了誓言的人要被炮烙，据说，死在炮烙之下的人，他们临死前嘴里只会喊:＂烫烫烫……＂。<br>&emsp;&emsp;好了，继续说，再比如他们学会了if、else、for，这些词代表控制，代表道德，代表法律，代表王权。王权说if 1，就是说这件事可以做，否则你只能做else下面的事。算法国的王只要说for，算法国的人就要一直埋头苦干，就算死在for循环里，只要王不说停，那就呆在循环里面不要出来。<br>&emsp;&emsp;语言的变更，有时候也会带来不安的思想。比如有人说，万物皆对象，这就宣扬了人人平等的观念。当然在王权统治的世界里是不被允许的，后来他们又换了种说法，说，一切皆函数。嗯，好像是好了许多。因为函数也是要分高等函数，低等函数的。这样就保留了阶级分层的概念，贵族认为他们还是贵族，贱民们虽然还是贱民，但是他们也能仰起头说，对不起，要调用我之前，请先声明。看，这就是函数们的尊严。<br>&emsp;&emsp;当然我不是说高级语言是万恶之源，工具没有错的。我想说，有了高级语言当然也有了很多新问题，比如高级语言里面有字符，有词，多个字符可以组成一个词，每个词都代表不同的含义。算法国用惯了1和0。虽然他们摒弃了1和0的表达方式，但是他们的思维却扎根在上面，他们不懂语法，也很难理解上下文，他们只知道，哪个词代表哪个意思，所以为了理解这一整个句子到底是什么意思，他们得先从句子里面找词，理解词就理解了句子。这就有了字符串匹配的需求。</p>
<h4 id="朴素的字符串匹配"><a href="#朴素的字符串匹配" class="headerlink" title="朴素的字符串匹配"></a>朴素的字符串匹配</h4><p>&emsp;&emsp;算法国首先想到的是最简单朴素的匹配算法，比如在字符串ABCABCDABABCD中匹配ABCDABC：</p>
<p><strong>第一次匹配</strong>：</p>
<table>
<thead>
<tr>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center"><font color="#E91E63">A</font></th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">A</td>
<td style="text-align:center">B</td>
<td style="text-align:center">C</td>
<td style="text-align:center"><font color="#E91E63">D</font></td>
<td style="text-align:center">A</td>
<td style="text-align:center">B</td>
<td style="text-align:center">C</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
</tbody>
</table>
<p><strong>第二次匹配</strong>：</p>
<table>
<thead>
<tr>
<th style="text-align:center">A</th>
<th style="text-align:center"><font color="#E91E63">B</font></th>
<th style="text-align:center">C</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"></td>
<td style="text-align:center"><font color="#E91E63">A</font></td>
<td style="text-align:center">B</td>
<td style="text-align:center">C</td>
<td style="text-align:center">D</td>
<td style="text-align:center">A</td>
<td style="text-align:center">B</td>
<td style="text-align:center">C</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
</tbody>
</table>
<p><strong>第三次匹配</strong>：</p>
<table>
<thead>
<tr>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center"><font color="#E91E63">C</font></th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"><font color="#E91E63">A</font></td>
<td style="text-align:center">B</td>
<td style="text-align:center">C</td>
<td style="text-align:center">D</td>
<td style="text-align:center">A</td>
<td style="text-align:center">B</td>
<td style="text-align:center">C</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
</tbody>
</table>
<p>每次匹配失败，当前模式串往后移动一格，直到匹配成功或者超出主串范围。</p>
<h4 id="KMP算法"><a href="#KMP算法" class="headerlink" title="KMP算法"></a>KMP算法</h4><p>&emsp;&emsp;在朴素的匹配算法中，第一次匹配的时候匹配了ABC，直到A的时候，发现两者无法匹配，这时候朴素算法选择前进一格。按照我们常人的思维，在已知了主串是ABCA的情况下，模式串为什么还要如此保守地前进一格？完全可以前进三格，因为ABCA中只有最后的A才能与模式串匹配。所以第二次匹配就变成了这样：</p>
<p><strong>第二次匹配</strong></p>
<table>
<thead>
<tr>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center"><font color="#E91E63">A</font></th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center">A</td>
<td style="text-align:center">B</td>
<td style="text-align:center">C</td>
<td style="text-align:center">D</td>
<td style="text-align:center">A</td>
<td style="text-align:center">B</td>
<td style="text-align:center"><font color="#E91E63">C</font></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
</tbody>
</table>
<p>&emsp;&emsp;KMP算法就是利用已匹配的字符串来让算法国的国民少走一些格子。为了使用已匹配的字符串来计算可以跳过的格子，在KMP算法中，有一张部分匹配表（Partial Match Table）作为参照。部分匹配表是针对模式串的，比如ABCDABC的部分匹配表如下：</p>
<table>
<thead>
<tr>
<th style="text-align:center">已匹配字符串</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">部分匹配值</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
<td style="text-align:center">0</td>
<td style="text-align:center">1</td>
<td style="text-align:center">2</td>
<td style="text-align:center">3</td>
</tr>
</tbody>
</table>
<p>ABCDABC可以产生如下几种匹配方式：A、AB、ABC、ABCD、ABCDA、ABCDAB、ABCDABC。即有可能开始A匹配上了，但是后面匹配不上，或者开始AB匹配上了，后面的又匹配不上……部分匹配表中的匹配值，指的是每种匹配方式，前后最长的共有元素的个数：</p>
<ol>
<li>A无共有元素，所以A的部分匹配值为0</li>
<li>AB无共有元素，所以AB的部分匹配值为0</li>
<li>ABC无共有元素，所以ABC的部分匹配值为0</li>
<li>ABCD无共有元素，所以ABCD的部分匹配值为0</li>
<li>ABCDA，前缀A和后缀A是最长的共有元素，所以ABCDA的部分匹配值为1</li>
<li>ABCDAB，前缀AB和后缀AB是最长的共有元素，所以ABCDAB的部分匹配值为2</li>
<li>ABCDABC，前缀ABC和后缀ABC是最长的共有元素，所以ABCDABC的部分匹配值为3</li>
</ol>
<p>&emsp;&emsp;我们可以按照自己的思维作一下推论，假设模式串中的ABCD和主串都匹配上了，但是后面的字符不匹配，此时模式串无论移到主串BCD的哪个位置上显然都是无法匹配的，因为我们已知A与BCD都无法匹配，即模式串需要移动4格；假设ABCDA都匹配上了，我们可以很轻松得出模式串应该移动到主串的A位置上，因为他们两个可以匹配，即模式串需要移动4格……有了部分匹配表，算法国的人也可以很轻松地根据已匹配的字符串得出模式串移动的格子，可以按照下面的公式去计算：</p>
<p><center><strong>移动的格子数 = 已匹配的字符串数 - 部分匹配值</strong></center><br>&emsp;&emsp;已匹配的字符串ABCDA数量5，查表可知ABCDA的部分匹配值为1，移动格子为4，再与我们之前的推论对比一下，模式串移动的格子数正好是一致的。</p>
<h4 id="BM算法"><a href="#BM算法" class="headerlink" title="BM算法"></a>BM算法</h4><p>&emsp;&emsp;KMP算法很巧妙，但是还是不够快。因为我们只能利用已匹配字符的信息来进行跳格。试想着从主串的头部开始比较，如果第一个字符串就无法匹配，整个模式串只能前进一格，因为主串后面的信息我们无法得知。BM算法就打破了朴素的字符串匹配算法以及KMP算法的桎梏，他选择从模式串的尾部开始匹配：</p>
<p><strong>第一次匹配</strong>:</p>
<table>
<thead>
<tr>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center"><font color="#E91E63">E</font></th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">A</td>
<td style="text-align:center">B</td>
<td style="text-align:center">D</td>
<td style="text-align:center"><font color="#E91E63">A</font></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
</tbody>
</table>
<p>第一次匹配从模式串的后缀开始，比较E和A。不一致，E就称为坏字符。这时候在模式串中检查是否有坏字符E。如果模式串中没有E，这时候模式串可以很轻松地大步跳过E。如果有的话，需要把此位置移动到坏字符的位置，保持对齐。可以根据坏字符得到一个移动格子数的公式：<center><strong>移动的格子数 = 坏字符相对模式串的位置 - 模式串中此位置从右往左出现的第一个坏字符的位置</strong></center>比如坏字符E相对模式串的位置为3（以下位置计数皆从0开始），从E的位置开始从右往左找，在模式串中未出现，所有计为-1。可以得出移动的格子数为4：</p>
<p><strong>第二次匹配</strong>：</p>
<table>
<thead>
<tr>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">E</th>
<th style="text-align:center">B</th>
<th style="text-align:center"><font color="#E91E63">C</font></th>
<th style="text-align:center"><font color="#2196F3">D</font></th>
<th style="text-align:center"><font color="#2196F3">A</font></th>
<th style="text-align:center">B</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center">A</td>
<td style="text-align:center"><font color="#E91E63">B</font></td>
<td style="text-align:center"><font color="#2196F3">D</font></td>
<td style="text-align:center"><font color="#2196F3">A</font></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
</tbody>
</table>
<p>第二次匹配的时候，发现DA都匹配，B和C不匹配，我们称DA、A为好后缀。所有从尾部匹配的字符串都是好后缀，比如有匹配的字符串ABCD，那么ABCD、BCD、CD、D都是好后缀。这时候按照坏字符的规则来跳格子，坏字符C相对模式串的位置为1，坏字符C在模式串中出现的位置为-1，移动的格子数为2。但其实按照我们的思维来看，这时候应该移动3个格子才是最佳的。坏字符的移动规则在这里显然不是最优的，这时候我们可以借助好后缀。可以设想如果模式串未匹配的字符中没有出现好后缀，那么，模式串完全可以跳过好后缀前进。同理如果出现了好后缀，那么相同的字符串只要中间对齐即可。根据好后缀规则可以得到一个计算格子数的公式：</p>
<p><center><strong>移动的格子数 = 模式串的字符个数 - 1 - Max(最长好后缀在模式串中出现的最接近右边的位置, 其他好后缀在头部的位置)</strong></center>解释一下这个公式：</p>
<ol>
<li>最长好后缀在模式串中出现的最接近右边的位置，不能是最右边，即保证移动的格子数不能为0。优先匹配最长好后缀。</li>
<li>除了最长的好后缀，其他的好后缀必须保证在头部。比如非最长好后缀AB在模式串ABDA中的位置为1；比如非最长好后缀AB在模式串CBDA中的位置，因为头部无AB，所以位置为-1</li>
<li>计算好后缀在模式串中的位置时，从0开始以最后一个字符的位置为准，比如有模式串ABDADA，假设最长好后缀为DA，那么DA在模式串ABDADA中最接近右边的位置为3。</li>
</ol>
<p>按照好后缀的公式来计算一下跳的格子，最长好后缀DA在模式串ABDA中没有可匹配的（不能匹配最右边的DA），所以位置为-1，其他好后最A在模式串ABDA头部的位置为0，所以这里取0，模式串ABDA长度为4，最终计算跳格子的数量为3，跟先前预估的最佳方案一致。</p>
<p><strong>第三次匹配</strong>：</p>
<table>
<thead>
<tr>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">E</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">A</th>
<th style="text-align:center"><font color="#E91E63">B</font></th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center">A</td>
<td style="text-align:center">B</td>
<td style="text-align:center">D</td>
<td style="text-align:center"><font color="#E91E63">A</font></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
</tbody>
</table>
<p>A和B不匹配，B为坏字符，按照坏字符公式，可以很快得出模式串需要移动2格：</p>
<p><strong>第四次匹配</strong>：</p>
<table>
<thead>
<tr>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">E</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center"><font color="#E91E63">D</font></th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center">A</td>
<td style="text-align:center">B</td>
<td style="text-align:center">D</td>
<td style="text-align:center"><font color="#E91E63">A</font></td>
</tr>
</tbody>
</table>
<p>&emsp;&emsp;当然如果移动的格子超过主串的长度，本次匹配就结束了。以上，可以看出坏字符和好后缀其实都是针对于模式串的，所以其实我们可以像KMP算法中那样，可以预先生成一个坏字符和好后缀的“部分匹配表“。然后根据好后缀规则和坏字符规则公式来计算每一次移动格子数的一个最优解。</p>
<h4 id="Sunday算法"><a href="#Sunday算法" class="headerlink" title="Sunday算法"></a>Sunday算法</h4><p>&emsp;&emsp;BM算法已经很快了，不过在算法国的眼里，快无止境。Sunday算法就再一次诠释了这个理念。Sunday算法和BM算法的原理其实差不多，不过Sunday算法是从头开始匹配的，当字符无法匹配的时候，它会选择主串与模式串对应的最后一个字符的下一个字符，进行匹配。</p>
<p><strong>第一次匹配</strong>:</p>
<table>
<thead>
<tr>
<th style="text-align:center"><font color="#E91E63">D</font></th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">A</th>
<th style="text-align:center"><font color="#2196F3">E</font></th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"><font color="#E91E63">A</font></td>
<td style="text-align:center">B</td>
<td style="text-align:center">D</td>
<td style="text-align:center">A</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
</tbody>
</table>
<p>D和A无法匹配，这时候选择主串与模式串相对应的最后一个字符的下一个字符来匹配，即在模式串中查找E是否存在，如果E不存在，模式串可以大步直接跳过E。当下一个字符完全匹配不上的时候，可以得出一个公式：<center><strong>移动的格子数 = 模式串的字符个数 + 1</strong></center>这里可以跳5格：</p>
<p><strong>第二次匹配</strong>:</p>
<table>
<thead>
<tr>
<th style="text-align:center">D</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">A</th>
<th style="text-align:center">E</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center"><font color="#E91E63">A</font></th>
<th style="text-align:center">B</th>
<th style="text-align:center"><font color="#2196F3">A</font></th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center">A</td>
<td style="text-align:center">B</td>
<td style="text-align:center"><font color="#E91E63">D</font></td>
<td style="text-align:center">A</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
</tbody>
</table>
<p>本次A和B都能匹配，发现A和D无法匹配，再次比较主串中的下一个字符A是否在模式串中，如果在的话，选择一个最近的匹配，将模式串与主串基于这个A字符对齐。当下一个字符可以在模式串中搜索到的时候，可以得出一个公式（位置从0开始）：<center><strong>移动的格子数 = 模式串的字符个数 - 下一个字符在模式串中出现的最靠右的位置</strong></center>本次只需要移动1格：</p>
<p><strong>第三次匹配</strong>:</p>
<table>
<thead>
<tr>
<th style="text-align:center">D</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">A</th>
<th style="text-align:center">E</th>
<th style="text-align:center">A</th>
<th style="text-align:center"><font color="#E91E63">B</font></th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">A</th>
<th style="text-align:center"><font color="#2196F3">B</font></th>
<th style="text-align:center">C</th>
<th style="text-align:center">D</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"><font color="#E91E63">A</font></td>
<td style="text-align:center">B</td>
<td style="text-align:center">D</td>
<td style="text-align:center">A</td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
</tr>
</tbody>
</table>
<p>发现B和A无法匹配，查看B在模式串中的位置，并与模式串中最近的B字符对齐，本次需要移动3格：</p>
<p><strong>第四次匹配</strong>:</p>
<table>
<thead>
<tr>
<th style="text-align:center">D</th>
<th style="text-align:center">B</th>
<th style="text-align:center">C</th>
<th style="text-align:center">A</th>
<th style="text-align:center">E</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center">A</th>
<th style="text-align:center">B</th>
<th style="text-align:center"><font color="#E91E63">C</font></th>
<th style="text-align:center">D</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center"></td>
<td style="text-align:center">A</td>
<td style="text-align:center">B</td>
<td style="text-align:center"><font color="#E91E63">D</font></td>
<td style="text-align:center">A</td>
</tr>
</tbody>
</table>
<p>&emsp;&emsp;KMP算法利用已匹配字符的信息，解决朴素算法一次不匹配只能跳一格的缺陷，但是当字符都匹配不上的时候，KMP也无能为力。而BM算法使得在无字符可以匹配的情况下，甚至可以大大加速模式串的移动。在这一点上，Sunday算法发扬光大，当无字符匹配的时候，它突破了BM算法最多只能移动模式串位数的限制。</p>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/算法国/" rel="tag"># 算法国</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2018/12/17/RocketMQ之旅（六）broker启动/" rel="next" title="RocketMQ之旅（六）broker启动">
                <i class="fa fa-chevron-left"></i> RocketMQ之旅（六）broker启动
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2019/02/01/RocketMQ之旅（七）broker处理消息/" rel="prev" title="RocketMQ之旅（七）broker处理消息">
                RocketMQ之旅（七）broker处理消息 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  
    <div class="comments" id="comments">
      <div id="disqus_thread">
        <noscript>
          Please enable JavaScript to view the
          <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a>
        </noscript>
      </div>
    </div>

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">matrix</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives">
              
                  <span class="site-state-item-count">47</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">18</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                
                  <span class="site-state-item-count">19</span>
                  <span class="site-state-item-name">标签</span>
                
              </div>
            

          </nav>

          

          

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-4"><a class="nav-link" href="#很长的开头"><span class="nav-number">1.</span> <span class="nav-text">很长的开头</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#朴素的字符串匹配"><span class="nav-number">2.</span> <span class="nav-text">朴素的字符串匹配</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#KMP算法"><span class="nav-number">3.</span> <span class="nav-text">KMP算法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#BM算法"><span class="nav-number">4.</span> <span class="nav-text">BM算法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#Sunday算法"><span class="nav-number">5.</span> <span class="nav-text">Sunday算法</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">matrix</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Pisces</a> v5.1.4</div>
<div class=BbeiAn-info">
  浙ICP备 -
  <a href="http://www.beian.miit.gov.cn">18040498号</a>
  </a>
</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  

    
      <script id="dsq-count-scr" src="https://luyun.disqus.com/count.js" async></script>
    

    
      <script type="text/javascript">
        var disqus_config = function () {
          this.page.url = 'http://yoursite.com/2018/12/17/算法国（二）字符串匹配/';
          this.page.identifier = '2018/12/17/算法国（二）字符串匹配/';
          this.page.title = '算法国（二）字符串匹配';
        };
        var d = document, s = d.createElement('script');
        s.src = 'https://luyun.disqus.com/embed.js';
        s.setAttribute('data-timestamp', '' + +new Date());
        (d.head || d.body).appendChild(s);
      </script>
    

  




	





  














  





  

  

  

  
  

  

  

  

</body>
</html>
